LintCode Notes | Hi, Jenny

####1.Rectangle Overlap
【consider exceptions】 1. x2太左了、太右了； 2. y2太上了、太下了

####2.Longest Palindrome
【Hashset】

 一边装一边丢;
 count + 2 ;
 if(size != 0) ,count+1

####3.Maximum Subtree
【设置全局变量TreeNode result 和Int max】

需要helper是因为原函数返回TreeNode，需要helper返回int，
为什么一定要返回int ？ 这就是helper最后不能直接返回max，
而是root.val + right + left 的原因----->
因为我们全部扫了一遍，即使这个root不是最优值，我们也在往上面扫，所以往上传的是当前root的sum。

####5.Decode Way

f[n]=f[n-1](条件s[n]!=0) + f[n-2](条件是s[n-1]与s[n]组成的数字在10-26之间)

####6.K Closest Points
【PriorityQueue】

    globalOrigin = origin;
    PriorityQueue<Point> queue = new PriorityQueue<Point>(k, new Comparator<Point>() {
        public int compare(Point a, Point b) {
            //注意这里的globalorigin。如果用origin的话会报错：
            //local variable origin is accessed from within inner class; needs to be declared final
            //origin是个本地变量，被内建class访问时，需要在外面declare？
            int diff = getDistance(b, globalOrigin) - getDistance(a, globalOrigin);
            if(diff == 0) {
                diff = b.x - a.x;
            }
            if (diff == 0) {
                diff = b.y - a.y;
            }
            return diff;
        }
    });

####7.Copy List with Random Pointer

####8.Window Sum

1. 求某一段和： s[j] - s[k -1] 
2. 求S[i] ： s[i] = s[i - 1] + a[i] 
3. 节省空间
法1. 链表保存sum
法2. 数组滚动

####9. Check Word Abbreviation

情况1.出现数字 while里面套while，计算num
情况2.未出现数字 if (s[++] ！= a[++])

####10. Words Abbreviation

所有string 的 prefix initial is 1，
use Hashmap to count repeated 
use while to scan ans[] 很多很多遍，
each time, check ans[i] in map whether count > 1 
never mind the old string in map, Because  we scan the ans[] ,not map.
注意挪动的是prefix，所以每次传入缩写函数的是dict而不是ans。

####11 Mirror Numbers

1.使用Map存储pair
2.用int[256] 来代替map存储char，节省空间！

####12 Sliding Window
idea : 1. use queue
sum = sum + val - queue.pop()

2. use sum[100000] instead of queue
sum[n~n+size] = sum[n+size] - sum[n]
id ++
3. use scroll: use mod to get id,
actual_id = id % (size + 1);
Eg: size = 3, id : 0,1,2,3,4,5 
actual_id : 0 , 1, 2, 3 ,0,
(here we initial sum = [size + 1])
so that sum[actual_id] = sum[actual_id  - 1] + val
still : sum[n~n+size] = sum[n+size] - sum[n]

####13. Edit Distance
if( == ) {( i,j ) = (i - 1, j - 1)}
else{ (i, j) = min[ (i - 1,j) ,(i , j - 1), (i - 1, j-1) ] }

####14. Edit Distance2
if(n > m){ return isOneEditDistance(t, s);}

####15. Roman to Integer

1. except : 4 ,9, 40 ,90, 400, 900 ,others are all : left > right --->left+right
2. if left < right : right - left
3. use dict/map to store dictionary------> use switch instead
4. avoid discuss the last one:  
  every for-loop

####16.Integer to Roman
四个list就搞定了

####17 Strings Serialization
不适用StringBuilder的话，会time exceed
String 字符串常量
StringBuffer 字符串变量（线程安全）
StringBuilder 字符串变量（非线程安全）
简要的说， String 类型和 StringBuffer 类型的主要性能区别其实在于 String 是不可变的对象, 因此在每次对 String 类型进行改变的时候其实都等同于生成了一个新的 String 对象，然后将指针指向新的 String 对象，所以经常改变内容的字符串最好不要用 String ，因为每次生成对象都会对系统性能产生影响，特别当内存中无引用对象多了以后， JVM 的 GC 就会开始工作，那速度是一定会相当慢的。
而如果是使用 StringBuffer 类则结果就不一样了，每次结果都会对 StringBuffer 对象本身进行操作，而不是生成新的对象，再改变对象引用。所以在一般情况下我们推荐使用 StringBuffer

先说一下集合的故事，HashTable是线程安全的，很多方法都是synchronized方法，而HashMap不是线程安全的，但其在单线程程序中的性能比HashTable要高。
StringBuffer和StringBuilder类的区别也是如此，他们的原理和操作基本相同，区别在于StringBufferd支持并发操作，线性安全的，适合多线程中使用。StringBuilder不支持并发操作，线性不安全的，不适合多线程中使用。新引入的StringBuilder类不是线程安全的，但其在单线程中的性能比StringBuffer高。

####18 Read Character from file
buffer 有多少读多少/读完了再清空

####19. Substring Anagrams
use num to store char
differencial == 0
sliding window to miles & add

####20. Two Strings Are Anagrams

####21. Word Abbreviation Set
用count>2的方法会time limit，因为你用了两个hashmap
用一个hashmap>

####22 Longest Consecutive Sequence
// Can not sort —> no sorting algorithm time complexity is O(n)
// 对于每一个nums[i],向左右延伸
// 为什么延伸完了这一段可以remove？因为这一段必然和其他线段是断开的

Identify Celebrity
Load Balancer
Convert BST to Greater Tree
Binary Tree Leaves Order Traversal
Binary Tree Flipping
Inorder Successor in Binary Search Tree
Word Break II